//
//  ViewController.m
//  TestGit
//
//  Created by LDH on 2018/3/22.
//  Copyright © 2018年 LDH. All rights reserved.
//

#import "ViewController.h"

@interface ViewController ()

@property (nonatomic, strong) NSMutableArray *unSortedArray;

@end

@implementation ViewController

- (void)viewDidLoad {
    [super viewDidLoad];
    // Do any additional setup after loading the view, typically from a nib.
    
    self.unSortedArray = [NSMutableArray new];
    for (NSInteger i = 0; i <100; i++) {
        NSInteger idx = arc4random() % 100;
        [self.unSortedArray addObject:[NSNumber numberWithInteger:idx]];
    }
    
    NSLog(@"%@", self.unSortedArray);
    [self bubbleSort:self.unSortedArray];
    [self selectSort:self.unSortedArray];
    NSLog(@"%@", self.unSortedArray);
}

// 冒泡排序
- (void)bubbleSort:(NSMutableArray *)arr
{
    for (int i = 0; i < arr.count; i++) {
        for (int j = 0; j < arr.count - i - 1;j++) {
            if ([arr[j+1] integerValue] < [arr[j] integerValue]) {
                int temp = [arr[j] intValue];
                arr[j] = arr[j + 1];
                arr[j + 1] = [NSNumber numberWithInt:temp];
            }
        }
    NSLog(@"%@", self.unSortedArray);
    }
}

/**
 * 最优时间复杂度 O(n²)
 * 最坏时间复杂度 O(n²)
 * 稳定性：不稳定（考虑升序每次选择最大的情况）
 */
- (void)selectSort:(NSMutableArray *)arr {
    
    for (int i = 0; i < arr.count - 1; i++) { // 比较的次数 [0,count-1) [0,1,2,3]
        int min_index = i;
        for (int j = i; j < arr.count; j++) { // 比较的元素
            if (arr[min_index] > arr[j]) {
                min_index = j;
            }
        }
        NSNumber *temp = arr[i];
        arr[i] = arr[min_index];
        arr[min_index] = temp;
    }
}

@end
